/*
 * @lc app=leetcode.cn id=1202 lang=javascript
 *
 * [1202] 交换字符串中的元素
 */

// @lc code=start
/**
 * @param {string} s
 * @param {number[][]} pairs
 * @return {string}
 */
function swip(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

class UnionSet {
  constructor (n = 100) {
    this.father = new Array(n);
    for (let i = 0; i < n; i++) this.father[i] = i;
  }
  // 带路径压缩
  find(x) {
    return this.father[x] = (this.father[x] == x ? x : this.find(this.father[x]));
  }
  // 将 a 合并到 b
  merge(a, b) {
    this.father[this.find(a)] = this.find(b);
  }
  query(a, b) {
    return this.find(a) === this.find(b);
  }
}

var smallestStringWithSwaps = function (s, pairs) {
  let arr = s.split('');
  const u = new UnionSet(arr.length);
  for (let i = 0; i < pairs.length; i++) {
    // 按索引分集合
    u.merge(pairs[i][0], pairs[i][1]);
  }

  // 超时
  // for (let i = 0; i < arr.length; i++) {
  //   for (let j = i + 1; j < arr.length; j++) {
  //     if(u.query(i, j) && arr[i] > arr[j]) swip(arr, i, j);
  //   }
  // }

  // 分组
  let group = {};
  for (let i = 0; i < arr.length; i++) {
    if (!group[u.find(i)]) group[u.find(i)] = [];
    group[u.find(i)].push(arr[i]);
  }

  for (let key in group) {
    group[key].sort((a, b) => a.charCodeAt() - b.charCodeAt());
  }

  //通过原始字符坐标, 查找其所在组号, 然后取其组最前面字符进行拼接
  let p = {}; // 记录各组取字符串的位置 
  let ans = '';

  for (let i = 0; i < arr.length; i++) {
    let fi = u.find(i);
    if (!p[fi]) p[fi] = 0;
    ans += group[fi][p[fi]];

    p[fi]++;
  }// 拼接字符

  return ans;
};
// @lc code=end

